package lc20240602;

import lc20240521.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author 不知名帅哥
 * @version 1.0
 * @description 验证是否是二叉搜索树。
 * @date 2024/6/2 16:25
 */
public class CheckIsBST {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.right = new TreeNode(6);
        root.left = new TreeNode(3, new TreeNode(2, new TreeNode(1), null), new TreeNode(4));
        CheckIsBST checkIsBST = new CheckIsBST();
//        System.out.println(checkIsBST.isValidBST(root));
        System.out.println(checkIsBST.isBinarySearchTree(root));
    }

    Deque<Integer> stack = new ArrayDeque<>();

    public boolean isValidBST(TreeNode root) {
        inOrder(root);
        if (stack.isEmpty()) {
            return false;
        }
        if (stack.size() == 1) {
            return true;
        }
        while (!stack.isEmpty()) {
            int a = stack.pop();
            if (stack.peek() != null) {
                if (a <= stack.peek()) {
                    return false;
                }
            }
        }
        return true;
    }

    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        stack.push(root.val);
        inOrder(root.right);
    }

//    static int lower;
//    static int upper;
    //递归解法
    public boolean isBinarySearchTree(TreeNode root){
        int low=Integer.MIN_VALUE;
        int high=Integer.MAX_VALUE;
        return isBST(root,low,high);
    }
    public static boolean isBST(TreeNode root,int lower,int upper){
        if (root==null){
            return true;
        }

        if (root.val<=lower||root.val>=upper){
            return false;
        }
        return isBST(root.left,lower,root.val)&&isBST(root.right,root.val,upper);
    }

}
